package com.github.kezhenxu94.playground.java.interview.xiaomi;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

// TODO Unfinished
public class XiaoMiTreeHeight {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int nodesCount = sc.nextInt();
		Map<Integer, Tuple> nodes = new HashMap<>();
		for (int i = 0; i < nodesCount - 1; i++) {
			int pid = sc.nextInt();
			Tuple t = nodes.getOrDefault(pid, new Tuple());
			t.set(new TreeNode(sc.nextInt()));
			nodes.put(pid, t);
		}
		TreeNode buildTree = buildTree(nodes);
		test(buildTree);
		height(buildTree, 0);
		sc.close();
	}

	private static TreeNode buildTree(Map<Integer, Tuple> nodes) {
		TreeNode root = new TreeNode(0);
		List<TreeNode> ps = new ArrayList<>();
		ps.add(root);
		while (!ps.isEmpty()) {
			TreeNode p = ps.remove(0);
			System.out.println(p);
			Tuple children = nodes.get(p.id);
			if (children == null)
				continue;
			TreeNode tmp;
			if ((tmp = children.get()) != null) {
				p.left = tmp;
				if (p.left != null)
					ps.add(p.left);
			}
			if ((tmp = children.get()) != null) {
				p.right = tmp;
				if (p.right != null)
					ps.add(p.right);
			}
		}
		return root;
	}

	private static void test(TreeNode n) {
		if (n != null) {
			System.out.println(n.id);
			test(n.left);
			test(n.right);
		}
	}

	private static int height(TreeNode root, int heightSoFar) {
		if (root == null)
			return heightSoFar;
		heightSoFar++;
		return Math.max(height(root.left, heightSoFar), height(root.right, heightSoFar));
	}

	static class TreeNode {
		TreeNode left;
		TreeNode right;
		int id;

		public TreeNode(int id) {
			this.id = id;
		}
	}

	static class Tuple {
		TreeNode first;
		TreeNode second;

		public void set(TreeNode node) {
			if (first == null)
				first = node;
			else
				second = node;
		}

		public TreeNode get() {
			TreeNode result = first;
			if (result != null)
				first = null;
			else {
				result = second;
				second = null;
			}
			return result;
		}
	}
}
